/**
 * 构建单链表
 * 先定义一个Node类用来存储结点的值域和指针域
 * 即当前结点中的值和后面结点的方法
 * 在c中就是相当于定义一个结构体类型和一个数据域和指针域的方法
 */
package com.xuwei.base.link;

/*
 *定义一个链表主类，并且定义链表的各种操作方法
 *能力：创建单链表，遍历打印链表，插入值，删除值，查询值
 * 
 */
public class SingleLink {

	public LNode head;// 定义一个头结点

	/**
	 * 定义一个创建链表的方法 该方法称之为：尾插法（后插法）：新产生的结点从尾部插入链表
	 */
	public void createLink(int[] a) {
		LNode pnew;// 表示产生新结点
		LNode ptail = new LNode();// 为尾结点分配堆内存
		head = ptail;// 初始化是头结点与尾结点相等
		for (int i = 0; i < a.length; i++) {
			pnew = new LNode();// 为新产生的结点分配堆内存
			pnew.setData(a[i]);// 传递data值
			ptail.setNext(pnew);// 把新产生的结点设置为ptail的后继结点
			pnew.setNext(null);// 把新产生的结点的后继结点设为空
			ptail = pnew;// 移动ptail结点的位置使之一直指向尾部

		}
	}

	/**
	 * 定义判断链表中的元素是否存在的方法
	 * 
	 */
	public void searchLink(int value) {
		LNode ptr;
		ptr = head.getNext();
		while (ptr != null)// 在结点非空的情况下寻找匹配的值
		{
			if (value == ptr.getData())// 匹配成功
			{
				System.out.println("找到数据：" + ptr.getData());
				break;// 退出循环
			} else // 当目前值不是要查找的值时，查找下一个
			{
				ptr = ptr.getNext();
			}

		}
		// 链表遍历完毕，没找到匹配
		if (ptr == null) {
			System.out.println("链表中无要查找的值！");
		}
	}

	/**
	 * 定义一个删除结点的方法
	 */
	public void deleteLink(int value) {
		LNode ptr;
		LNode p;
		p = head;
		ptr = head.getNext();

		while (ptr != null) {
			// 判断链表中的当前值是否是要删除的结点
			if (value == ptr.getData()) {
				// 把ptr的后继结点设置为p的后继结点，即形式上在链表中删除了ptr结点
				p.setNext(ptr.getNext());
				System.out.println("删除数据" + value + "成功！");
				break;
			} else {
				p = ptr;// p指向ptr的位置
				ptr = ptr.getNext();// ptr指向其直接后继的位置
			}
		}

		if (ptr == null) {
			System.out.println("链表中没有要删除的数据！");
		}
	}

	/**
	 * 定义插入结点的方法
	 */
	public void insertLink(int pos, int value)// 两个参数，一个表示插入的位置，另一个表示插入的值
	{
		LNode ptr;
		LNode pnew;// 实例化新结点
		ptr = head.getNext();
		while (ptr != null) {
			if (pos == ptr.getData())// 按值查找位置
			{
				pnew = new LNode();
				pnew.setData(value);
				pnew.setNext(ptr.getNext());
				ptr.setNext(pnew);
				System.out.println("插入数据" + value + "成功！");
				break;
			} else {
				ptr = ptr.getNext();
			}
		}

		if (ptr == null) {
			System.out.println("插入数据失败！");
		}
	}

	/**
	 * 定义一个输出链表内容方法
	 */
	public void printLink() {
		LNode ptr;// 实例化一个结点
		ptr = head.getNext();// 该结点取得头结点的后继结点
		while (ptr != null) {
			System.out.print(ptr.getData() + "->");
			ptr = ptr.getNext();
		}

		System.out.println("Null");
	}

	/**
	 * 测试用例，用数组创建一个整型的链表，并且把它输出
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int a[] = new int[10];
		for (int i = 0; i < a.length; i++) {
			a[i] = i;
		}
		SingleLink list = new SingleLink();
		list.createLink(a);
		// System.out.println("测试链表输出如下：");
		// list.printLink();

		// list.insertLink(6, 66);
		// list.insertLink(66,34);
		// list.deleteLink(34);
		// list.deleteLink(66);

		// list.searchLink(9);

		// System.out.println("插入元素后链表的输出如下：");
		list.printLink();
	}

}
